package com.ai.zuochengyun.phase01.class01;

import java.util.Arrays;

/**
 * 计数排序
 */
public class Code17_CountSort {
    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }

        // 找到序列中最大的数
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }

        // 建立一个桶，统计词频
        int[] bucket = new int[max + 1];
        for (int num : arr) {
            bucket[num]++;
        }

        // 从左到右，按统计的个数，将对应的下标值倒出来
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }


    public static void test(int[] arr) {
        Arrays.sort(arr);
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * (maxValue+1));
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
    }

    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean suc = true;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);

            test(arr1);
            countSort(arr2);

            if (!isEquals(arr1, arr2)) {
                suc = false;
                System.out.println("oops");
                printArray(arr1);
                System.out.println();
                printArray(arr2);
                break;
            }
        }
        System.out.println("排序结束");
    }
}
